home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Games / Xconq 7.1.0 / src / xconq-7.1.0 / kernel / mkterr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-07-07  |  32.0 KB  |  1,196 lines  |  [TEXT/R*ch]
  1. /* Terrain generation for Xconq.
  2.    Copyright (C) 1986, 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996
  3.    Stanley T. Shebs.
  4.  
  5. Xconq is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation; either version 2, or (at your option)
  8. any later version.  See the file COPYING.  */
  9.  
  10. /* This is the collection of terrain generation methods. */
  11.  
  12. /* Fractal terrain generation. */
  13.  
  14. /* The process is actually done for elevation and water separately, then
  15.    the terrain type is derived from looking at both together. */
  16.  
  17. #include "conq.h"
  18.  
  19. /* This bounds the range of high and low spots. */
  20.  
  21. #define MAXALT 4000
  22.  
  23. /* The following dynamically allocated arrays must be ints, since a area
  24.    may have >32K cells. */
  25.  
  26. int *histo;             /* histogram array */
  27. int *alts;              /* percentile for each elevation */
  28. int *wets;              /* percentile for level of moisture */
  29.  
  30. /* Area scratch layers are used as: relief = tmp1, moisture = tmp2,
  31.    aux = tmp3 */
  32.  
  33. int stepsize = 20;
  34.  
  35. int partdone;
  36.  
  37. /* This variable records the number of cells that didn't match any of the
  38.    terrain type percentiles. */
  39.  
  40. static int numholes;
  41.  
  42. static void make_blobs PARAMS ((short *layer, int numblobs, int blobradius, int blobalt));
  43. static void limit_layer PARAMS ((short *layer, int hi, int lo));
  44. static void smooth_layer PARAMS ((short *layer, int times));
  45. static void percentile PARAMS ((short *layer, int *percentiles));
  46. static void compose_area PARAMS ((void));
  47. static int terrain_from_percentiles PARAMS ((int x, int y));
  48. static int dig_maze_path PARAMS ((int x1, int y1, int dir1));
  49. static int num_open_adj PARAMS ((int x, int y));
  50. static int random_solid_terrain PARAMS ((void));
  51. static int random_room_terrain PARAMS ((void));
  52. static int random_passage_terrain PARAMS ((void));
  53. static int high_point PARAMS ((int x, int y));
  54. static int water_point PARAMS ((int x, int y));
  55. static int bay_point PARAMS ((int x, int y));
  56. static void set_room_interior PARAMS ((int x, int y));
  57. static void name_highest_peaks PARAMS ((Obj *parms));
  58. static void name_lakes PARAMS ((Obj *parms));
  59. static char *name_feature_at PARAMS ((int x, int y, char *typename));
  60. static char *name_feature_at_using PARAMS ((Obj *namerlist, int x, int y, char *typename));
  61. static void fix_adjacent_terrain PARAMS ((void));
  62. static void flatten_liquid_terrain PARAMS ((void));
  63. static void set_edge_values PARAMS ((int x, int y, int t));
  64.  
  65. /* The main function goes through a heuristically-determined process */
  66. /* (read: I dinked until I liked the results) to make a area. */
  67.  
  68. /* Should add a cheap erosion simulator. */
  69.  
  70. int
  71. make_fractal_terrain(calls, runs)
  72. int calls, runs;
  73. {
  74.     int actualcells, altnumblobs, altblobradius, altblobalt;
  75.     int wetnumblobs, wetblobradius, wetblobalt;
  76.  
  77.     /* Don't run if terrain is already present. */
  78.     if (terrain_defined())
  79.       return FALSE;
  80.     /* Note that we may still want this even if only one ttype defined,
  81.        since elevs may still vary usefully. */
  82.     /* Heuristic limit - this algorithm would get weird on small areas */
  83.     if (area.width < 9 || area.height < 9) {
  84.     init_warning("cannot generate fractal terrain for a %d x %d area, must be at least 9x9",
  85.              area.width, area.height);
  86.     return FALSE;
  87.     }
  88.     Dprintf("Going to make fractal terrain ...\n");
  89.     allocate_area_scratch(3);
  90.     histo  = (int *) xmalloc(MAXALT * sizeof(int));
  91.     alts   = (int *) xmalloc(MAXALT * sizeof(int));
  92.     wets   = (int *) xmalloc(MAXALT * sizeof(int));
  93.     announce_lengthy_process("Making fractal terrain");
  94.     /* Need a rough estimate of how much work involved, so can do progress. */
  95.     if (g_alt_blob_density() > 0) {
  96.     actualcells = (g_alt_blob_size() * area.numcells) / 10000;
  97.     altblobradius = isqrt((actualcells * 4) / 3) / 2;
  98.     altnumblobs = (g_alt_blob_density() * area.numcells) / 10000;
  99.     altblobalt = g_alt_blob_height();
  100.     }
  101.     if (g_wet_blob_density() > 0) {
  102.     actualcells = (g_wet_blob_size() * area.numcells) / 10000;
  103.     wetblobradius = isqrt((actualcells * 4) / 3) / 2;
  104.     wetnumblobs = (g_wet_blob_density() * area.numcells) / 10000;
  105.     wetblobalt = g_wet_blob_height();
  106.     }
  107.     if (g_alt_blob_density() > 0) {
  108.     /* Build a full relief area. */
  109.     partdone = 0;
  110.     make_blobs(area.tmp1, altnumblobs, altblobradius, altblobalt);
  111.     /* Run the requested number of smoothing steps. */
  112.     partdone += stepsize;
  113.     smooth_layer(area.tmp1, g_alt_smoothing());
  114.     percentile(area.tmp1, alts);
  115.     }
  116.     if (g_wet_blob_density() > 0) {
  117.     /* Build a "moisture relief" area. */
  118.     partdone += stepsize;
  119.     make_blobs(area.tmp2, wetnumblobs, wetblobradius, wetblobalt);
  120.     partdone += stepsize;
  121.     smooth_layer(area.tmp2, g_wet_smoothing());
  122.     percentile(area.tmp2, wets);
  123.     }
  124.     /* Put it all together. */
  125.     partdone += stepsize;
  126.     compose_area();
  127.     fix_adjacent_terrain();
  128.     add_edge_terrain();
  129.     flatten_liquid_terrain();
  130.     /* Free up what we don't need anymore. */
  131.     free(histo);
  132.     free(alts);
  133.     free(wets);
  134.     finish_lengthy_process();
  135.     /* Report on the substitutions made. */
  136.     if (numholes > 0) {
  137.     init_warning("no possible terrain for %d cells, made them into %s",
  138.              numholes, t_type_name(0));
  139.     }
  140.     return TRUE;
  141. }
  142.  
  143. static void
  144. make_blobs(layer, numblobs, blobradius, blobalt)
  145. short *layer;
  146. int numblobs, blobradius, blobalt;
  147. {
  148.     int x0, y0, x1, y1, x2, y2, updown, x, y, xw;
  149.     int maxdz, i, dz, oz;
  150.  
  151.     /* Init everything to the middle of the raw altitude range. */
  152.     for_all_cells(x, y)
  153.       aset(layer, x, y, MAXALT/2);
  154.     numblobs = max(1, numblobs);
  155.     maxdz = min(max(1, blobalt), MAXALT/2);
  156.     Dprintf("Making %d blobs of radius %d max-dz %d...\n",
  157.         numblobs, blobradius, maxdz);
  158.     /* Now lay down blobs. */
  159.     for (i = 0; i < numblobs; ++i) {
  160.     if (i % 100 == 0) {
  161.         announce_progress(partdone + (stepsize * i) / numblobs);
  162.     }
  163.     /* Decide whether we're making a hole or a hill. */
  164.     updown = (flip_coin() ? 1 : -1);
  165.     /* Pick a center for the bump. */
  166.     random_point(&x0, &y0);
  167.     if (blobradius <= 0) {
  168.         /* Special case for one-cell blobs. */
  169.         aadd(layer, x0, y0, updown * maxdz);
  170.     } else {
  171.         /* Compute the LL corner. */
  172.         x1 = x0 - blobradius;  y1 = y0 - blobradius;
  173.         /* Compute the UR corner. */
  174.         x2 = x0 + blobradius;  y2 = y0 + blobradius;
  175.         /* Raise/lower all the cells within this bump. */
  176.         for (y = y1; y <= y2; ++y) {
  177.         for (x = x1; x <= x2; ++x) {
  178.             xw = wrapx(x);
  179.             if ((x - x1 + y - y1 > blobradius)
  180.             && (x2 - x + y2 - y > blobradius)) {
  181.             /* skip points outside the area */
  182.             if (in_area(x, y)) {
  183.                 oz = aref(layer, xw, y);
  184.                 /* Add some variation within the bump. */ 
  185.                 dz = updown * (maxdz + xrandom(maxdz/2));
  186.                 /* If dz is really extreme, cut it down. */
  187.                 if (!between(0, oz + dz, MAXALT))
  188.                   dz /= 2;
  189.                 if (!between(0, oz + dz, MAXALT))
  190.                   dz /= 2;
  191.                 aset(layer, xw, y, oz + dz);
  192.             }
  193.             }
  194.         }
  195.         }
  196.     }
  197.     }
  198.     /* Adding and subtracting might have got out of hand. */
  199.     limit_layer(layer, MAXALT-1, 0); 
  200. }
  201.  
  202. /* Ensure that area values stay within given range. */
  203.  
  204. static void
  205. limit_layer(layer, hi, lo)
  206. short *layer;
  207. int hi, lo;
  208. {
  209.     int x, y, m;
  210.     
  211.     for_all_cells(x, y) {
  212.     m = aref(layer, x, y);
  213.     aset(layer, x, y, max(lo, min(m, hi)));
  214.     }
  215. }
  216.  
  217. /* Average each cell with its neighbors, using tmp3 as scratch layer. */
  218.  
  219. static void
  220. smooth_layer(layer, times)
  221. short *layer;
  222. int times;
  223. {
  224.     int i, x, y, nx, px, dir, x1, y1, ndirs, sum;
  225.  
  226.     for (i = 0; i < times; ++i) {
  227.     Dprintf("Smoothing...\n");
  228.     for (x = 0; x < area.width; ++x) {
  229.         nx = wrapx(x + 1);
  230.         px = wrapx(x - 1);
  231.         for (y = 0; y < area.height; ++y) {
  232.         if (in_area(x, y)) {
  233.             sum = aref(layer, x, y);
  234.             if (inside_area(x, y) /* and hex geometry */) {
  235.             sum += aref(layer,  x, y + 1);
  236.             sum += aref(layer, nx, y);
  237.             sum += aref(layer, nx, y - 1);
  238.             sum += aref(layer,  x, y - 1);
  239.             sum += aref(layer, px, y);
  240.             sum += aref(layer, px, y + 1);
  241.             sum /= (NUMDIRS + 1);
  242.             } else {
  243.             /* Otherwise, use a slower but more general algorithm. */
  244.             ndirs = 0;
  245.             for_all_directions(dir) {
  246.                 if (point_in_dir(x, y, dir, &x1, &y1)) {
  247.                 sum += aref(layer, x1, y1);
  248.                 ++ndirs;
  249.                 }
  250.             }
  251.             if (ndirs > 0)
  252.               sum /= (ndirs + 1);
  253.             }
  254.             set_tmp3_at(x, y, sum);
  255.         }
  256.         }
  257.     }
  258.     for (x = 0; x < area.width; ++x) {
  259.         for (y = 0; y < area.height; ++y) {
  260.         aset(layer, x, y, tmp3_at(x, y));
  261.         }
  262.     }
  263.     announce_progress(partdone + (stepsize * i) / times);
  264.     }
  265. }
  266.  
  267. /* Terrain types are specified in terms of percentage cover on a area, so
  268.    for instance the Earth is 70% sea.  Since each of several types will have
  269.    its own percentages (both for elevation and moisture), the simplest thing
  270.    to do is to calculate the percentile for each raw elevation and moisture
  271.    value, and save them all away.  */
  272.  
  273. /* Percentile computation is inefficient, should be done incrementally
  274.    somehow instead of with * and / */
  275.  
  276. static void
  277. percentile(layer, percentiles)
  278. short *layer;
  279. int *percentiles;
  280. {
  281.     int i, x, y, total;
  282.     
  283.     Dprintf("Computing percentiles...\n");
  284.     limit_layer(layer, MAXALT-1, 0);
  285.     for (i = 0; i < MAXALT; ++i) {
  286.     histo[i] = 0;
  287.     percentiles[i] = 0;
  288.     }
  289.     /* Make the basic histogram, counting only the inside. */
  290.     for_all_interior_cells(x, y) {
  291.     ++histo[aref(layer, x, y)];
  292.     }
  293.     /* Integrate over the histogram */
  294.     for (i = 1; i < MAXALT; ++i)
  295.     histo[i] += histo[i-1];
  296.     /* Total here should actually be same as number of cells in the area */
  297.     total = histo[MAXALT-1];
  298.     /* Compute the percentile position */
  299.     for (i = 0; i < MAXALT; ++i) {
  300.     percentiles[i] = (100 * histo[i]) / total;
  301.     }
  302. }
  303.  
  304. /* Final creation and output of the area. */
  305. /* (should reindent) */
  306. static void
  307. compose_area()
  308. {
  309.     int x, y, t, t2, t3;
  310.     int elev, elevrange[MAXTTYPES], elevlo[MAXTTYPES], elevhi[MAXTTYPES];
  311.     int rawelev, rawlo[MAXTTYPES], rawhi[MAXTTYPES], rawrange[MAXTTYPES];
  312.  
  313.     Dprintf("Assigning terrain types to cells...\n");
  314.     /* Make the terrain layer itself. */
  315.     allocate_area_terrain();
  316.     numholes = 0;
  317.     for_all_interior_cells(x, y) {
  318.     t = terrain_from_percentiles(x, y);
  319.     set_terrain_at(x, y, t);
  320.     }
  321.     if (!world_is_flat()) {
  322.         /* Compute elevation variations of terrain.  This works on interior
  323.            cells only; the edge gets handled later, by edge-specific code. */
  324.         for_all_terrain_types(t) {
  325.             elevrange[t] = t_elev_max(t) - t_elev_min(t);
  326.         rawlo[t] = rawhi[t] = -1;
  327.         }
  328.         if (!elevations_defined()) {
  329.         allocate_area_elevations();
  330.        }
  331.     for_all_interior_cells(x, y) {
  332.         t = terrain_at(x, y);
  333.         if (rawlo[t] < 0)
  334.           rawlo[t] = tmp1_at(x, y);
  335.         else
  336.           rawlo[t] = min(tmp1_at(x, y), rawlo[t]);
  337.         if (rawhi[t] < 0)
  338.           rawhi[t] = tmp1_at(x, y);
  339.         else
  340.           rawhi[t] = max(tmp1_at(x, y), rawhi[t]);
  341.     }
  342.     /* If the final elevation ranges for several terrain types
  343.        overlap, then they should all be considered as a group;
  344.        this is because the low raw values ought to become low
  345.        real elevations, and use the same scale as other terrain
  346.        types whose elevations are in the same or similar ranges.
  347.        The calculation below basically iterates over terrain types,
  348.        and since it is possible for two apparently disjoint ranges
  349.        to be "joined" later by another range that overlaps both,
  350.        we must iterate up to as many times as there are terrain
  351.        types. */
  352.     for_all_terrain_types(t) {
  353.         elevlo[t] = t_elev_min(t);
  354.         elevhi[t] = t_elev_max(t);
  355.     }
  356.     for_all_terrain_types(t) {
  357.       for_all_terrain_types(t3) {
  358.         for_all_terrain_types(t2) {
  359.         if (between(elevlo[t], elevlo[t2], elevhi[t])
  360.             || between(elevlo[t], elevhi[t2], elevhi[t])) {
  361.             elevlo[t] = min(elevlo[t], elevlo[t2]);
  362.             elevhi[t] = max(elevhi[t], elevhi[t2]);
  363.             rawlo[t] = min(rawlo[t], rawlo[t2]);
  364.             rawhi[t] = max(rawhi[t], rawhi[t2]);
  365.         }
  366.         }
  367.       }
  368.     }
  369.         for_all_terrain_types(t) {
  370.             rawrange[t] = rawhi[t] - rawlo[t];
  371.         }
  372.      for_all_interior_cells(x, y) {
  373.         t = terrain_at(x, y);
  374.         elev = 0;
  375.         if (elevrange[t] > 0) {
  376.         if (rawrange[t] > 0) {
  377.             rawelev = tmp1_at(x, y);
  378.             elev = (((rawelev - rawlo[t]) * elevrange[t]) / rawrange[t]);
  379.         } else {
  380.             elev = elevrange[t] / 2;
  381.         }
  382.         }
  383.         elev += t_elev_min(t);
  384.         /* Clip elevation to required bounds. */
  385.         if (elev < t_elev_min(t))
  386.           elev = t_elev_min(t);
  387.         if (elev > t_elev_max(t))
  388.           elev = t_elev_max(t);
  389.         set_elev_at(x, y, elev);
  390.     }
  391.     }
  392. }
  393.  
  394. /* Compute the actual terrain types.  This is basically a process of
  395.    checking the percentile limits on each type against what is actually
  396.    there. */
  397.  
  398. static int
  399. terrain_from_percentiles(x, y)
  400. int x, y;
  401. {
  402.     int t, rawalt = tmp1_at(x, y), rawwet = tmp2_at(x, y);
  403.  
  404.     if (numttypes == 1)
  405.       return 0;
  406.     for_all_terrain_types(t) {
  407.     if (t_is_cell(t)
  408.         && between(t_alt_min(t), alts[rawalt], t_alt_max(t))
  409.         && between(t_wet_min(t), wets[rawwet], t_wet_max(t))) {
  410.         return t;
  411.     }
  412.     }
  413.     /* No terrain maybe not an error, so just count and summarize later. */
  414.     ++numholes;
  415.     return 0;
  416. }
  417.  
  418. /* Totally random (with weighting) terrain generation, as well as
  419.    random elevations. */
  420.  
  421. int
  422. make_random_terrain(calls, runs)
  423. int calls, runs;
  424. {
  425.     int t, x, y, cellsum, cellsumtable[MAXTTYPES];
  426.     int i, numcells, n, elevrange, occur, dir;
  427.  
  428.     if (terrain_defined())
  429.       return FALSE;
  430.     announce_lengthy_process("Making random terrain");
  431.     Dprintf("Assigning terrain types...\n");
  432.     cellsum = 0;
  433.     for_all_terrain_types(t) {
  434.     if (t_is_cell(t)) {
  435.         cellsum += t_occurrence(t);
  436.     }
  437.     cellsumtable[t] = cellsum;
  438.     }
  439.     allocate_area_terrain();
  440.     /* Overwrite already-defined elevs? */
  441.     if (!elevations_defined() && !world_is_flat())
  442.       allocate_area_elevations();
  443.     i = 0;
  444.     numcells = area.width * area.height;
  445.     for_all_interior_cells(x, y) {
  446.     if (i++ % 100 == 0)
  447.       announce_progress((i * 100) / numcells);
  448.      n = xrandom(cellsum + 1);
  449.      for_all_terrain_types(t) {
  450.          if (n <= cellsumtable[t] && t_is_cell(t))
  451.            break;
  452.      }
  453.     set_terrain_at(x, y, t);
  454.     if (elevations_defined() && !world_is_flat()) {
  455.         elevrange = t_elev_max(t) - t_elev_min(t) + 1;
  456.         set_elev_at(x, y, xrandom(elevrange) + t_elev_min(t));
  457.     }
  458.     }
  459.     /* Make sure the edge of the area has something in it. */
  460.     add_edge_terrain();
  461.     /* Now maybe add borders and connections. */
  462.     for_all_terrain_types(t) {
  463.     switch (t_subtype(t)) {
  464.       case cellsubtype:
  465.         /* do nothing */
  466.         break;
  467.       case bordersubtype:
  468.         occur = t_occurrence(t);
  469.         if (occur > 0) {
  470.         for_all_interior_cells(x, y) {
  471.             for_all_directions(dir) {
  472.             if (xrandom(10000) < occur)
  473.               set_border_at(x, y, dir, t, 1);
  474.             }
  475.         }
  476.         }
  477.         break;
  478.       case connectionsubtype:
  479.         occur = t_occurrence(t);
  480.         if (occur > 0) {
  481.         for_all_interior_cells(x, y) {
  482.             for_all_directions(dir) {
  483.             if (xrandom(10000) < occur)
  484.               set_connection_at(x, y, dir, t, 1);
  485.             }
  486.         }
  487.         }
  488.         break;
  489.       case coatingsubtype:
  490.         /* (should do something here) */
  491.         break;
  492.     }
  493.     }
  494.     finish_lengthy_process();
  495.     return TRUE;
  496. }
  497.  
  498. /* Method that is wired to be as close to earth as possible. */
  499.  
  500. /* (need to compute scale, get avg elevation and rainfall) */
  501.  
  502. int seatype = -1;
  503. int landtype = -1;
  504.  
  505. int
  506. make_earthlike_terrain(calls, runs)
  507. int calls, runs;
  508. {
  509.     int t, x, y, elevrange;
  510.  
  511.     if (terrain_defined())
  512.       return FALSE;
  513.     Dprintf("Categorizing terrain types...\n");
  514.     for_all_terrain_types(t) {
  515.         if (strcmp("sea", t_type_name(t)) == 0)
  516.           seatype = t;
  517.         if (strcmp("plains", t_type_name(t)) == 0)
  518.           landtype = t;
  519.         /* etc */
  520.     }
  521.     if (seatype <= 0 || landtype <= 0) {
  522.         Dprintf("can't find earthlike terrain types");
  523.         return FALSE;
  524.     }
  525.     announce_lengthy_process("Making Earth-like terrain");
  526.     allocate_area_terrain();
  527.     /* Overwrite already-defined elevs? */
  528.     if (!elevations_defined() && !world_is_flat())
  529.       allocate_area_elevations();
  530.     elevrange = maxelev - minelev;
  531.     for_all_cells(x, y) {
  532.     if (inside_area(x, y)) {
  533.         set_terrain_at(x, y, (flip_coin() ? seatype : landtype));
  534.         if (elevations_defined() && !world_is_flat()) {
  535.             if (terrain_at(x, y) == seatype) {
  536.             set_elev_at(x, y, 0);
  537.             } else {
  538.             set_elev_at(x, y, xrandom(elevrange - 1) + 1);
  539.             }
  540.         }
  541.     }
  542.     }
  543.     /* Make sure the border of the area has something in it. */
  544.     add_edge_terrain();
  545.     finish_lengthy_process();
  546.     return TRUE;
  547. }
  548.  
  549. /* Maze terrain generation.  */
  550.  
  551. int numsolidtypes = 0;
  552. int numroomtypes = 0;
  553. int numpassagetypes = 0;
  554.  
  555. int sumsolidoccur = 0;
  556. int sumroomoccur = 0;
  557. int sumpassageoccur = 0;
  558.  
  559. int solidtype = NONTTYPE;
  560. int roomtype = NONTTYPE;
  561. int passagetype = NONTTYPE;
  562.  
  563. int numpassagecells = 0;
  564.  
  565. static void
  566. set_room_interior(x, y)
  567. int x, y;
  568. {
  569.     set_terrain_at(x, y, random_room_terrain());
  570. }
  571.  
  572. int
  573. make_maze_terrain(calls, runs)
  574. int calls, runs;
  575. {
  576.     int t, x, y, x1, y1, i;
  577.     int dir, n;
  578.     int numcells, tries = 0;
  579.     int roomcells, roomradius, numrooms;
  580.     int numsolidcells = 0, numpassagecellsneeded;
  581.  
  582.     if (terrain_defined())
  583.       return FALSE;
  584.     for_all_terrain_types(t) {
  585.         if ((n = t_occurrence(t)) > 0) {
  586.         sumsolidoccur += n;
  587.         ++numsolidtypes;
  588.         solidtype = t;
  589.         }
  590.         if ((n = t_maze_room_occurrence(t)) > 0) {
  591.         sumroomoccur += n;
  592.         ++numroomtypes;
  593.         roomtype = t;
  594.         }
  595.         if ((n = t_maze_passage_occurrence(t)) > 0) {
  596.         sumpassageoccur += n;
  597.         ++numpassagetypes;
  598.         passagetype = t;
  599.         }
  600.     }
  601.     if (numsolidtypes + numroomtypes + numpassagetypes < 2) {
  602.         init_warning("No types to make maze with");
  603.         return FALSE;
  604.     }
  605.     announce_lengthy_process("Making maze terrain");
  606.     allocate_area_terrain();
  607.     /* Fill in the area with solid terrain. */
  608.     for_all_cells(x, y) {
  609.     set_terrain_at(x, y, random_solid_terrain());
  610.     }
  611.     /* Set the edges properly. */
  612.     add_edge_terrain();
  613.     numcells = area.numcells;
  614.     if (g_maze_room() > 0) {
  615.     roomcells = 7;
  616.     roomradius = 1;
  617.     numrooms = ((numcells * g_maze_room()) / 10000) / roomcells;
  618.     for (i = 0; i < numrooms; ++i) {
  619.         random_point(&x1, &y1);
  620.         apply_to_area(x1, y1, roomradius, set_room_interior);
  621.     }
  622.     }
  623.     for_all_interior_cells(x, y) {
  624.         if (t_occurrence(terrain_at(x, y)) > 0) ++numsolidcells;
  625.     }
  626.     if (g_maze_passage() > 0) {
  627.       numpassagecellsneeded = (numcells * g_maze_passage()) / 10000;
  628.       while (numpassagecells < numpassagecellsneeded && tries++ < 500) {
  629.         random_point(&x1, &y1);
  630.         if (t_occurrence(terrain_at(x1, y1)) > 0) {
  631.         set_terrain_at(x1, y1, random_passage_terrain());
  632.         dir = random_dir();
  633.         dig_maze_path(x1, y1, dir);
  634.         dig_maze_path(x1, y1, opposite_dir(dir));
  635.         }
  636.       }
  637.     }
  638.     /* Make sure the border of the area is fixed up. */
  639.     add_edge_terrain();
  640.     finish_lengthy_process();
  641.     return TRUE;
  642. }
  643.  
  644. static int
  645. dig_maze_path(x1, y1, dir1)
  646. int x1, y1, dir1;
  647. {
  648.     int found;
  649.     int x, y, iter = 0, dir, dir2, nx, ny, nx2, ny2;
  650.     int dug = 0;
  651.     
  652.     while (!inside_area(x1+dirx[dir1], y1+diry[dir1])) {
  653.     dir1 = random_dir();
  654.     }
  655.     dir = dir1;
  656.     x = x1;  y = y1;
  657.     while (++iter < 500) {
  658.     point_in_dir(x, y, dir, &nx, &ny);
  659.     if (!inside_area(nx, ny))
  660.       break;
  661.     if (t_occurrence(terrain_at(nx, ny)) > 0
  662.         && num_open_adj(nx, ny) == 1) {
  663.         set_terrain_at(nx, ny, random_passage_terrain());
  664.         ++numpassagecells;
  665.         ++dug;
  666.     } else {
  667.         found = FALSE;
  668.         for_all_directions(dir2) {
  669.         point_in_dir(x, y, dir2, &nx2, &ny2);
  670.         if (inside_area(nx2, ny2)
  671.             && t_occurrence(terrain_at(nx2, ny2)) > 0
  672.             && num_open_adj(nx2, ny2) == 1) {
  673.             set_terrain_at(nx2, ny2, random_passage_terrain());
  674.             ++numpassagecells;
  675.             ++dug;
  676.             found = TRUE;
  677.             dir = dir2;
  678.             break;
  679.         }
  680.         }
  681.         if (!found) {
  682.         return dug;
  683.         }
  684.     }
  685.     if (probability(20)) {
  686.         dig_maze_path(nx, ny, left_dir(dir));
  687.         dig_maze_path(nx, ny, right_dir(dir));
  688.         return dug;
  689.     } else {
  690.         x = nx;  y = ny;
  691.         dir = (probability(50) ? dir : random_dir());
  692.     }
  693.     }
  694.     return dug;
  695. }
  696.  
  697. static int
  698. num_open_adj(x, y)
  699. int x, y;
  700. {
  701.     int dir, rslt = 0, nx, ny;
  702.  
  703.     for_all_directions(dir) {
  704.     point_in_dir(x, y, dir, &nx, &ny);
  705.     if (t_maze_room_occurrence(terrain_at(nx, ny)) > 0
  706.         || t_maze_passage_occurrence(terrain_at(nx, ny)) > 0) ++rslt;
  707.     }
  708.     return rslt;
  709. }
  710.  
  711. static int
  712. random_solid_terrain()
  713. {
  714.     if (numsolidtypes == 1)
  715.       return solidtype;
  716.     return (xrandom(numttypes));
  717. }
  718.  
  719. static int
  720. random_room_terrain()
  721. {
  722.     if (numroomtypes == 1)
  723.       return roomtype;
  724.     return (xrandom(numttypes));
  725. }
  726.  
  727. static int
  728. random_passage_terrain()
  729. {
  730.     if (numpassagetypes == 1)
  731.       return passagetype;
  732.     return (xrandom(numttypes));
  733. }
  734.  
  735. /* This method adds some randomly named geographical features. */
  736.  
  737. /* (This needs to interact properly with convex region finder eventually) */
  738.  
  739. int
  740. name_geographical_features(calls, runs)
  741. int calls, runs;
  742. {
  743.     char *classname;
  744.     Obj *rest;
  745.  
  746.     /* If we got features from file or somewhere, don't overwrite them. */
  747.     if (features_defined())
  748.       return FALSE;
  749.     /* We need to have some terrain to work from. */
  750.     if (!terrain_defined())
  751.       return FALSE;
  752.     /* If no feature types requested, don't make any. */
  753.     if (g_feature_types() == lispnil)
  754.       return FALSE;
  755.     announce_lengthy_process("Adding geographical features");
  756.     Dprintf("Adding geographical features...\n");
  757.     /* Set up the basic layer of data. */
  758.     init_features();
  759.     /* Scan through list to see what's being requested. */
  760.     for (rest = g_feature_types(); rest != lispnil; rest = cdr(rest)) {
  761.     if (consp(car(rest)) && stringp(car(car(rest)))) {
  762.         classname = c_string(car(car(rest)));
  763.         if (strcmp(classname, "peak") == 0) {
  764.             name_highest_peaks(cdr(car(rest)));
  765.         } else if (strcmp(classname, "lake") == 0) {
  766.         name_lakes(cdr(car(rest)));
  767.         } else {
  768.         run_warning("Don't know to identify \"%s\" features", classname);
  769.         }
  770.     } else {
  771.         run_warning("Clause not recognized");
  772.     }
  773.     }
  774.     finish_lengthy_process();
  775.     return TRUE;
  776. }
  777.  
  778. /* Identify the highest high points as "peaks". */
  779.  
  780. static void
  781. name_highest_peaks(parms)
  782. Obj *parms;
  783. {
  784.     int x, y;
  785.     int maxpeaks = (area.width * area.height) / 200;
  786.     int numpeaks, *peakx, *peaky, i, lo;
  787.     char *name;
  788.     Feature *mountain;
  789.  
  790.     if (!elevations_defined() || world_is_flat()) {
  791.     run_warning("Can't identify peaks, world is flat");
  792.     return;
  793.     }
  794.     peakx = (int *) xmalloc(maxpeaks * sizeof(int));
  795.     peaky = (int *) xmalloc(maxpeaks * sizeof(int));
  796.     numpeaks = 0;
  797.  
  798.     for_all_interior_cells(x, y) {
  799.     if (high_point(x, y)) {
  800.         if (numpeaks < maxpeaks) {
  801.         peakx[numpeaks] = x;  peaky[numpeaks] = y;
  802.         ++numpeaks;
  803.         } else {
  804.         /* Find the lowest of existing peaks. */
  805.         lo = 0;
  806.         for (i = 0; i < numpeaks; ++i) {
  807.             if (elev_at(peakx[i], peaky[i]) <
  808.             elev_at(peakx[lo], peaky[lo])) {
  809.             lo = i;
  810.             }
  811.         }
  812.         /* If less than our new candidate, replace. */
  813.         if (elev_at(x, y) > elev_at(peakx[lo], peaky[lo])) {
  814.             peakx[lo] = x;  peaky[lo] = y;
  815.         }
  816.         }
  817.     }
  818.     }
  819.     for (i = 0; i < numpeaks; ++i) {
  820.     name = name_feature_at(x, y, "peak");
  821.     if (name == NULL) {
  822.         sprintf(tmpbuf, "Pk %d", elev_at(peakx[i], peaky[i]));
  823.         name = copy_string(tmpbuf);
  824.     }
  825.     mountain = create_feature("peak", name);
  826.     mountain->size = 1;
  827.     set_raw_feature_at(peakx[i], peaky[i], mountain->id);
  828.     }
  829. }
  830.  
  831. /* True if xy is a local high point. */
  832.  
  833. static int
  834. high_point(x, y)
  835. int x, y;
  836. {
  837.     int dir, nx, ny;
  838.  
  839.     for_all_directions(dir) {
  840.     point_in_dir(x, y, dir, &nx, &ny);
  841.     if (elev_at(nx, ny) >= elev_at(x, y)) {
  842.         return FALSE;
  843.     }
  844.     }
  845.     return TRUE;
  846. }
  847.  
  848. static void
  849. name_lakes(parms)
  850. Obj *parms;
  851. {
  852.     int x, y;
  853.     char *name;
  854.     Feature *lake, *bay;
  855.  
  856.     for_all_interior_cells(x, y) {
  857.     if (water_point(x, y)) {
  858.         name = name_feature_at(x, y, "lake");
  859.         if (name != NULL) {
  860.         lake = create_feature("lake", name);
  861.         lake->size = 1;
  862.         set_raw_feature_at(x, y, lake->id);
  863.         }
  864.     } else if (bay_point(x, y)) {
  865.         name = name_feature_at(x, y, "bay");
  866.         if (name != NULL) {
  867.         bay = create_feature("bay", name);
  868.         bay->size = 1;
  869.         set_raw_feature_at(x, y, bay->id);
  870.         }
  871.     }
  872.     }
  873. }
  874.  
  875. /* True if xy is isolated water. */
  876.  
  877. static int
  878. water_point(x, y)
  879. int x, y;
  880. {
  881.     int dir, nx, ny;
  882.  
  883.     if (strcmp(t_type_name(terrain_at(x, y)), "sea") != 0
  884.         && strcmp(t_type_name(terrain_at(x, y)), "shallows") != 0)
  885.       return FALSE;
  886.     for_all_directions(dir) {
  887.     point_in_dir(x, y, dir, &nx, &ny);
  888.     if (terrain_at(x, y) == terrain_at(nx, ny) || t_liquid(terrain_at(nx, ny))) {
  889.         return FALSE;
  890.     }
  891.     }
  892.     return TRUE;
  893. }
  894.  
  895. static int
  896. bay_point(x, y)
  897. int x, y;
  898. {
  899.     int dir, nx, ny;
  900.     int seacount = 0, landcount = 0;
  901.  
  902.     if (strcmp(t_type_name(terrain_at(x, y)), "shallows") != 0)
  903.       return FALSE;
  904.     for_all_directions(dir) {
  905.     point_in_dir(x, y, dir, &nx, &ny);
  906.     if (strcmp(t_type_name(terrain_at(x, y)), "sea") == 0)
  907.       ++seacount;
  908.     else
  909.       ++landcount;
  910.     }
  911.     return (seacount > 0 && landcount > 2);
  912. }
  913.  
  914. static char *
  915. name_feature_at(x, y, typename)
  916. int x, y;
  917. char *typename;
  918. {
  919.     char *rslt;
  920.     Obj *namerlist;
  921.     Side *side;
  922.  
  923.     /* Look for any side-specific namers. */
  924.     if (people_sides_defined()) {
  925.     for_all_sides(side) {
  926.         if (side->featurenamers != NULL
  927.         && side->featurenamers != lispnil
  928.         && people_side_at(x, y) == side->id) {
  929.         rslt = name_feature_at_using(side->featurenamers, x, y, typename);
  930.         if (rslt != NULL)
  931.           return rslt;
  932.         }
  933.     }
  934.     }
  935.     /* Now try generic namer list. */
  936.     namerlist = g_feature_namers();
  937.     /* If no generic namers, get out of here. */
  938.     if (namerlist == lispnil)
  939.       return NULL;
  940.     return name_feature_at_using(namerlist, x, y, typename);
  941. }
  942.  
  943. static char *
  944. name_feature_at_using(namerlist, x, y, typename)
  945. Obj *namerlist;
  946. int x, y;
  947. char *typename;
  948. {
  949.     Obj *rest, *namerspec;
  950.  
  951.     /* If no namers found, get out of here. */
  952.     if (namerlist == lispnil)
  953.       return NULL;
  954.     for (rest = namerlist; rest != lispnil; rest = cdr(rest)) {
  955.     if (consp(car(rest))
  956.         && stringp(car(car(rest)))
  957.         && strcmp(c_string(car(car(rest))), typename) == 0) {
  958.         namerspec = cadr(car(rest));
  959.         /* This might be a string naming a namer, try making it into
  960.            a symbol. */
  961.         if (stringp(namerspec))
  962.           namerspec = intern_symbol(c_string(namerspec));
  963.             if (boundp(namerspec))
  964.           return run_namer(symbol_value(namerspec));
  965.         /* If the namer doesn't exist, then this will continue looking for
  966.            one that does, which is maybe good, because this might fall back
  967.            from a side-specific to a generic namer, but can be confusing to
  968.            game designers, because then a feature might be created with no
  969.            name, with no warning of a problem with namers. */
  970.     }
  971.     }
  972.     return NULL;
  973. }
  974.  
  975. /* Resolve any incompatibilities of terrain types in adjacent cells. */
  976. /* (should add code for borders and connections) */
  977.  
  978. static void
  979. fix_adjacent_terrain()
  980. {
  981.     int t1, t2, anyadjeffects, affected[MAXTTYPES];
  982.     int maxpasses, anychanges, x, y, t, dir, x1, y1, t3;
  983.  
  984.     anyadjeffects = FALSE;
  985.     for_all_terrain_types(t1) {
  986.     affected[t1] = FALSE;
  987.     for_all_terrain_types(t2) {
  988.         if (tt_adj_terr_effect(t1, t2) >= 0) {
  989.         anyadjeffects = TRUE;
  990.         affected[t1] = TRUE;
  991.         break;
  992.         }
  993.     }
  994.     }
  995.     if (!anyadjeffects)
  996.       return;
  997.     maxpasses = area.height;
  998.     while (maxpasses-- > 0) {
  999.     anychanges = FALSE;
  1000.     for_all_cells(x, y) {
  1001.         t = terrain_at(x, y);
  1002.         set_tmp1_at(x, y, t);
  1003.         if (affected[t]) {
  1004.         for_all_directions(dir) {
  1005.             if (point_in_dir(x, y, dir, &x1, &y1)) {
  1006.             t3 = tt_adj_terr_effect(t, terrain_at(x1, y1));
  1007.             if (t3 >= 0 && t3 != t) {
  1008.                 set_tmp1_at(x, y, t3);
  1009.                 anychanges = TRUE;
  1010.                 break;
  1011.             } 
  1012.             }
  1013.         }
  1014.         }
  1015.     }
  1016.     if (anychanges) {
  1017.         /* Copy from the tmp layer back to the area. */
  1018.         for_all_cells(x, y) {
  1019.         set_terrain_at(x, y, tmp1_at(x, y));
  1020.         }
  1021.     } else {
  1022.         /* No changes, things have stabilized; so return. */
  1023.         return;
  1024.     }
  1025.     }
  1026. }
  1027.  
  1028. /* For efficiency and semantics reasons, the methods might not assign values
  1029.    to the cells around the edge of the area (if there *are* edges; neither
  1030.    a torus nor sphere will have any).  Note that there is no way to
  1031.    disable this from the game module; if having nonconstant edges is important
  1032.    enough to be worth the user confusion, don't call this from your
  1033.    area generation method. */
  1034.  
  1035. void
  1036. add_edge_terrain()
  1037. {
  1038.     int x, y, t = g_edge_terrain(), halfheight = area.halfheight;
  1039.  
  1040.     /* Use ttype 0 if edge terrain is nonsensical. */
  1041.     if (!between(0, t, numttypes-1))
  1042.       t = 0;
  1043.     /* Right/left upper/lower sides of a hexagon. */
  1044.     if (!area.xwrap) {
  1045.     for (y = 0; y < halfheight; ++y) {
  1046.         /* SW edge */
  1047.         set_edge_values(halfheight - y, y, t);
  1048.         /* NW edge */
  1049.         set_edge_values(0, halfheight + y, t);
  1050.         /* SE edge */
  1051.         set_edge_values(area.width-1, y, t);
  1052.         /* NE edge */
  1053.         set_edge_values(area.width-1 - y, halfheight + y, t);
  1054.     }
  1055.     }
  1056.     /* Top and bottom edges of the area. */
  1057.     for (x = 0; x < area.width; ++x) {
  1058.     set_edge_values(x, 0, t);
  1059.     set_edge_values(x, area.height-1, t);
  1060.     }
  1061. }
  1062.  
  1063. static void
  1064. set_edge_values(x, y, t)
  1065. int x, y, t;
  1066. {
  1067.     int sumelev, numadj, dir, x1, y1, elev;
  1068.  
  1069.     set_terrain_at(x, y, t);
  1070.     /* Give it an average elevation. */
  1071.     if (elevations_defined()) {
  1072.     sumelev = 0;
  1073.     numadj = 0;
  1074.     for_all_directions(dir) {
  1075.         if (interior_point_in_dir(x, y, dir, &x1, &y1)) {
  1076.         sumelev += elev_at(x1, y1);
  1077.         ++numadj;
  1078.         }
  1079.     }
  1080.     /* It's possible that the caller is being sloppy and setting
  1081.        edge cells not actually in the area, so be cool about it. */
  1082.     if (numadj > 0) {
  1083.         elev = sumelev / numadj;
  1084.         /* Note that we clip only to overall bounds for the layer, not
  1085.            to the specific terrain type's bounds.  This is so that the
  1086.            edge terrain can be, say, ice, whose normal elevation range
  1087.            is high altitude, which would make a perspective view look
  1088.            weird (like peering into a sink). */
  1089.         if (elev < minelev)
  1090.           elev = minelev;
  1091.         if (elev > maxelev)
  1092.           elev = maxelev;
  1093.         set_elev_at(x, y, elev);
  1094.     }
  1095.     }
  1096. }
  1097.  
  1098. /* This makes area of liquid terrain types all have the same elevation, and an
  1099.    elevation less than that of any adjacent non-liquid terrain.  In simple terms,
  1100.    this makes ponds and such look right on contour maps (more importantly, LOS
  1101.    visibility will work as expected around water features). */
  1102.  
  1103. static void
  1104. flatten_liquid_terrain()
  1105. {
  1106.     int t1, t2, anyliquideffects, affected[MAXTTYPES];
  1107.     int maxpasses, anychanges, x, y, dir, x1, y1, highest, lowest;
  1108.  
  1109.     if (!elevations_defined() || world_is_flat())
  1110.       return;
  1111.     anyliquideffects = FALSE;
  1112.     for_all_terrain_types(t1) {
  1113.     affected[t1] = t_liquid(t1);
  1114.     if (affected[t1])
  1115.       anyliquideffects = TRUE;
  1116.     }
  1117.     if (!anyliquideffects)
  1118.       return;
  1119.     /* First raise up low places in all-liquid areas. */
  1120.     maxpasses = area.height;
  1121.     while (maxpasses-- > 0) {
  1122.     anychanges = FALSE;
  1123.     for_all_cells(x, y) {
  1124.         t1 = terrain_at(x, y);
  1125.         if (affected[t1]) {
  1126.         highest = elev_at(x, y);
  1127.         for_all_directions(dir) {
  1128.             if (point_in_dir(x, y, dir, &x1, &y1)) {
  1129.             t2 = terrain_at(x1, y1);
  1130.             if (affected[t2]) {
  1131.                 highest = max(highest, elev_at(x1, y1));
  1132.             } else {
  1133.                 goto nextcell;
  1134.             }
  1135.             }
  1136.         }
  1137.         /* Now we have the highest of liquid elevations. */
  1138.         if (highest != elev_at(x, y)) {
  1139.             set_elev_at(x, y, highest);
  1140.             anychanges = TRUE;
  1141.         }
  1142.         for_all_directions(dir) {
  1143.             if (point_in_dir(x, y, dir, &x1, &y1)) {
  1144.             t2 = terrain_at(x1, y1);
  1145.             if (affected[t2] && highest != elev_at(x1, y1)) {
  1146.                 set_elev_at(x1, y1, highest);
  1147.                 anychanges = TRUE;
  1148.             } 
  1149.             }
  1150.         }
  1151.         }
  1152.       nextcell:
  1153.         ;
  1154.     }
  1155.     if (!anychanges)
  1156.       break;
  1157.     }
  1158.     /* Now bring up all too-high places that are adjacent to non-liquid
  1159.        terrain. */
  1160.     maxpasses = area.height;
  1161.     while (maxpasses-- > 0) {
  1162.     anychanges = FALSE;
  1163.     for_all_cells(x, y) {
  1164.         t1 = terrain_at(x, y);
  1165.         if (affected[t1]) {
  1166.         lowest = elev_at(x, y);
  1167.         for_all_directions(dir) {
  1168.             if (point_in_dir(x, y, dir, &x1, &y1)) {
  1169.             t2 = terrain_at(x1, y1);
  1170.             if (affected[t2]) {
  1171.                 lowest = min(lowest, elev_at(x1, y1));
  1172.             } 
  1173.             }
  1174.         }
  1175.         /* Now we have the lowest of liquid elevations. */
  1176.         if (lowest != elev_at(x, y)) {
  1177.             set_elev_at(x, y, lowest);
  1178.             anychanges = TRUE;
  1179.         }
  1180.         for_all_directions(dir) {
  1181.             if (point_in_dir(x, y, dir, &x1, &y1)) {
  1182.             t2 = terrain_at(x1, y1);
  1183.             if (affected[t2] && lowest != elev_at(x1, y1)) {
  1184.                 set_elev_at(x1, y1, lowest);
  1185.                 anychanges = TRUE;
  1186.             } 
  1187.             }
  1188.         }
  1189.         }
  1190.     }
  1191.     if (!anychanges)
  1192.       break;
  1193.     }
  1194. }
  1195.  
  1196.